home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / sys / amiga / programmer / 6147 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.4 KB  |  54 lines
  1. Newsgroups: comp.sys.amiga.programmer
  2. Path: news.ifm.liu.se!liuida!news
  3. From: c92manen@und.ida.liu.se (Mans Engman)
  4. Subject: Re: Sorting a list
  5. X-Nntp-Posting-Host: astmatix.ida.liu.se
  6. Message-ID: <1958.6657T325T1880@und.ida.liu.se>
  7. Sender: news@ida.liu.se
  8. Organization: CIS Dept, Linkoping University, Sweden
  9. X-Newsreader: THOR 2.22 (Amiga;TCP/IP) *UNREGISTERED*
  10. References: <272.6650T63T1340@sn.no> <ZZNYYD.96Mar21121908@diku.dk> <xUqu7MD1A7alz7@0dietmar.tomate.tng.oche.de>
  11. Date: Sun, 24 Mar 1996 04:25:37 GMT
  12.  
  13.  
  14. >You could use a simple modification of bubble sort to boost performance to
  15. >the speed of QuickSort: use a dynamic interval instead of comparing
  16. >neighbours only. In the first pass, you would compare element <a> to
  17. >element <a + distance> and swap them if the order is wrong. Distance is
  18. >reduced after processing all elements. To be continued until the distance
  19. >is <1> (standard bubble sort) and the order is correct.
  20.  
  21. This "modified bubble sort" is actually a special case of an algorithm
  22. called shell sort. It's a very interesting algorithm, for more than one
  23. reason: It's easy to implement, with very little overhead. It's fast. It's
  24. completely impossible to analyse! :)
  25.  
  26. Some comments: The algorithm for sorting the "slices" of elements should be
  27. one that will sort an almost-sorted or completetly sorted sequence very fast.
  28. So bubble sort is actually a much better choice than quicksort :)
  29. However insertion sort is usually a little bit better in this case.
  30. Then there's the question of how many passes the algorithm should do, and what
  31. "distances" should be used. This may be fine-tuned for optimal performance on
  32. a certain number of elements, and the overhead of the implementation.
  33. For instance, a usually nice sequence of distances is 1, 3, 7, 15, 31...
  34. This results in O(n^1.5) time complexity (worst-case).
  35.  
  36. But completely OTOH since we were really talking strings and not algorithm
  37. theory, I'd suggest either a radix sort or combined bin+quick sort...
  38.  
  39. >* In a random sampling of GoldED users, 100% said that they'd rather use
  40. >  GoldED than be publically flogged, eaten alive by pirhanas, OR watch
  41. >  SeaQuest DSV.
  42.  
  43. Hmmm!!
  44. This sounds a bit like Macintosh marketing, doesn't it? :)
  45.  
  46. >/\/\ GoldED Support: http://www.clearlight.com/~dietmar
  47. >/\/\ E-Mail:         dietmar@tomate.tng.oche.de
  48. >/\/\ Fileserver:     dietmar@clearlight.com (subject: send file info)
  49. >     Phone/FAX:      +49-(0)241-81665-(Pause)-22
  50.  
  51.  
  52. /Mans (.sig being recompiled)
  53.  
  54.